import random
import time
from typing import List
from collections import deque

class Solution:
    def find1(self, nums: List[int], k: int) -> int:
        nums.sort(reverse=True)
        return nums[k-1]
    
    def find2(self, nums: List[int], k: int) -> int:
        stack = deque()
        
        for num in nums:
            # 如果栈为空或者栈的大小小于k，直接入栈
            if len(stack) < k:
                stack.append(num)
                # 保持栈是降序的
                stack = deque(sorted(stack, reverse=True))
            # 如果当前数大于栈顶的最小值，更新栈
            elif num > stack[-1]:
                stack.pop()
                stack.append(num)
                stack = deque(sorted(stack, reverse=True))
        
        return stack[-1]
n = random.randint(10000, 100000)
k = random.randint(1, n)

nums = [random.randint(0, 100000) for _ in range(n)]

sol = Solution()

start1 = time.time()
result1 = sol.find1(nums, k)
end1 = time.time()
runtime1 = (end1-start1)*1000

start2 = time.time()
result2 = sol.find2(nums.copy(), k)
end2 = time.time()
runtime2 = (end2-start2)*1000

print(f"生成的数组大小n: {n}")
print(f"选择的k值: {k}")
print(f"\n排序方法:")
print(f"第{k}大的数是: {result1}")
print(f"运行时间: {runtime1:.6f} 毫秒")
print(f"\n压缩栈方法:")
print(f"第{k}大的数是: {result2}")
print(f"运行时间: {runtime2:.6f} 毫秒")